//
//  main.c
//  eightMoney
//
//  Created by zhuoooo on 2022/5/30.
//  Copyright © 2022年 zhuoooo. All rights reserved.
//

#include <stdio.h>
#define N 10000

int sum(int all[],int n);
int Coin_two(int coin[],int right);
int Coin_three(int coin[]);
void FenDui(int all[],int a[],int b[],int c[],int d[],int n);
int Coin_n(int all[],int a[],int b[],int c[],int d[],int n);

int main(int argc, const char * argv[]) {
    int n;
    int all[N];
    int a[N],b[N],c[N],d[N];
    int i,res;
    printf("请输入硬币个数：\n");
    scanf("%d",&n);
    printf("请输入每个硬币的重量：\n");
    for(i=0;i<n;i++){
        scanf("%d",&all[i]);
    }
    
    /*for(i=0;i<n;i++){
     printf("%4d\n",all[i]);
     }*/
    //FenDui(all,a,b,c,d,n);
    res=Coin_n(all,a,b,c,d,n);
    printf("第%d个",res);
}


//同样分为三堆，外加一个余数堆，余数只能是2,3
//计算数组的和
int sum(int all[],int n)
{
    int result=0;
    int i;
    for(i=0;i< n;i++)
        result+=all[i];
    return result;
}
//两枚硬币
int Coin_two(int coin[],int right)
{
    int temp=0;
    if(coin[0]!=right){
        temp=0;
    }else{
        temp=1;
    }
    return temp;
}
//三枚硬币
int Coin_three(int coin[])
{
    int temp=0;
    if(coin[0]==coin[1]&&coin[0]!=coin[2]){
        temp=2;
    }
    else if(coin[0]==coin[2]&&coin[0]!=coin[1]){
        temp=1;
    }
    else if(coin[1]==coin[2]&&coin[0]!=coin[1])
        temp=0;
    
    return temp;
}
void FenDui(int all[],int a[],int b[],int c[],int d[],int n)
{
    int j=(n-n%3)/3;   //每一碓硬币数
    int k=n%3;   //余数个数
    int w=0;
    int i;
    for(i=0;i<j;i++)   //a数组（第一堆）硬币
    {
        a[i]=all[i];
    }
    printf("第一堆硬币数量为：%d 枚\n",j);
    
    for(i=j;i<2*j;i++)   //b数组（第二堆） 硬币
    {
        b[w]=all[i];
        w++;
    }
    printf("第二堆硬币数量为：%d 枚\n",j);
    w=0;
    for(i=2*j;i<3*j;i++)  //c数组（第三堆） 硬币
    {
        c[w]=all[i];
        w++;
    }
    printf("第三堆硬币数量为：%d 枚\n",j);
    w=0;
    if(k!=0){    //余数堆硬币
        for(i=3*j;i<3*j+k;i++)
        {
            d[w]=all[i];
            w++;
        }
        printf("余数堆硬币数量为：%d 枚\n",k);
    }
    else{
        for(i=0;i<k;i++){
            d[i]=0;
        }
        printf("余数堆硬币数量为0枚\n");
    }
}

int Coin_n(int all[],int a[],int b[],int c[],int d[],int n){
    int rem,temp=0;//余数
    int sum1,sum2,sum3,sum4;
    int m=(n-n%3)/3;
    FenDui(all,a,b,c,d,n);
    rem=n%3;
    sum1=sum(a,m);
    sum2=sum(b,m);
    sum3=sum(c,m);
    //printf("sum1=%d\n",sum1);
    //printf("sum2=%d\n",sum2);
    //printf("sum3=%d\n",sum3);
    //sum3=sum(all,c,b+1)-sum1-sum2;
    if(sum1==sum2)
    {
        if(sum3==sum2)
        {
            printf("假币在第四堆中的\n");
            if(rem==1) {
                return 0;
            }else if(rem==2) {
                temp=Coin_two(d,all[0]);//all[0]必定为真
                return temp;
            }else if(rem==3) {
                temp=Coin_three(d);
                return temp;
            }
            if(rem>3)  {
                printf("\n");
                return Coin_n(d,a,b,c,d,rem);
            }   //用减治法迭代
        }else{
            printf("假币在第三堆中的\n");
            if(m==1) {
                return 0;
            }else if(m==2) {
                temp=Coin_two(c,all[0]);//all[0]必定为真
                return temp;
            }else if(m==3) {
                temp=Coin_three(c);
                return temp;
            }
            if(m>3)  {
                printf("\n");
                return Coin_n(c,a,b,c,d,m);
            }
        }
    }else{
        if(sum3==sum2)
        {
            printf("假币在第一堆中的\n");
            if(m==1)
            {
                return 0;
            }else if(m==2)
            {
                temp=Coin_two(a,all[n-1]);//all[n-1]必定为真
                return temp;
            }else if(m==3)
            {
                temp=Coin_three(a);
                return temp;
            }
            if(m>3)
            {
                printf("\n");
                return Coin_n(a,a,b,c,d,m);
            }   //用减治法迭代
        }else
        {
            printf("假币在第二堆中的");
            if(m==1)
            {
                return b[0];
            }else if(m==2)
            {
                temp=Coin_two(b,all[0]);//all[0]必定为真
                return temp;
            }else if(m==3)
            {
                temp=Coin_three(b);
                return temp;
            }
            if(m>3)
            {
                printf("\n");
                return Coin_n(b,a,b,c,d,m);
            }
        }
    }
    return 0;
}

